Monotonic Stack

Monotonic Stack is a special type of stack.

What is a Monotonic Stack?

A monotonic stack is a special type of stack data structure in which the elements always maintain a monotonic increasing or decreasing order. When inserting a new element, the stack pops out all the elements at the top that do not satisfy the monotonicity, and then the new element is pushed onto the stack.

Types of Monotonic Stacks

Monotonic Increasing Stack

In a monotonic increasing stack, each element is larger than the one below it. When a new element is pushed onto the stack, if the top element of the stack is greater than or equal to the new element, the top element is popped out until the top element is smaller than the new element or the stack is empty.

Pseudocode

\begin{algorithm} \caption{Monotonic Stack for Finding the Next Greater Element} \begin{algorithmic} \Procedure{NextGreaterElement}{$nums$} \State $stack \gets \emptyset$ \Comment{Initialize an empty stack} \State $result \gets$ array of size $|nums|$ filled with $-1$ \Comment{Initialize result array with -1}

\For{$i \gets 0$ \To $|nums| - 1$}
  \While{$stack$ is not empty and $nums[stack.top()] < nums[i]$}
    \State $index \gets stack.pop()$
    \State $result[index] \gets nums[i]$
  \EndWhile
  \State $stack.push(i)$
\EndFor
\State \Return $result$

\EndProcedure
\end{algorithmic}
\end{algorithm}

Java Implement

import java.util.Stack;

public class MonotonicStack {
    public int[] nextGreaterElements(int[] nums) {
        int[] result = new int[nums.length];
        Stack<Integer> stack = new Stack<>();
        
        // Initialize result with -1
        for (int i = 0; i < nums.length; i++) {
            result[i] = -1;
        }

        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                result[stack.pop()] = nums[i];
            }
            stack.push(i);
        }

        return result;
    }

    public static void main(String[] args) {
        MonotonicStack ms = new MonotonicStack();
        int[] nums = {2, 1, 2, 4, 3};
        int[] result = ms.nextGreaterElements(nums);
        for (int val : result) {
            System.out.print(val + " ");
        }
    }
}

Monotonic Decreasing Stack

In a monotonic decreasing stack, each element is smaller than the one below it. When a new element is pushed onto the stack, if the top element is smaller than or equal to the new element, the top element is popped out until the top element is greater than the new element or the stack is empty.

Pseudocode

\begin{algorithm} \caption{Monotonic Decreasing Stack for Sliding Window Maximum} \begin{algorithmic} \Procedure{SlidingWindowMax}{$nums, k$} \State $deque \gets \emptyset$ \Comment{Initialize an empty deque} \State $result \gets$ array of size $|nums| - k + 1$

\For{$i \gets 0$ \To $|nums| - 1$}
  \Comment{Remove elements out of window}
  \If{$deque$ is not empty and $deque.front() \leq i - k$}
    \State $deque.pop\_front()$
  \EndIf

  \Comment{Maintain decreasing order in the deque}
  \While{$deque$ is not empty and $nums[deque.back()] < nums[i]$}
    \State $deque.pop\_back()$
  \EndWhile

  \State $deque.push\_back(i)$

  \Comment{Store the current window maximum}
  \If{$i \geq k - 1$}
    \State $result[i - k + 1] \gets nums[deque.front()]$
  \EndIf
\EndFor

\State \Return $result$

\EndProcedure
\end{algorithmic}
\end{algorithm}

Java Implement

import java.util.Deque;
import java.util.LinkedList;

public class SlidingWindowMax {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];
        
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            // Remove elements not in the sliding window
            if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }

            // Remove elements smaller than the current number from the back
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            deque.offerLast(i);

            // The front of the deque is the max element of the window
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }

        return result;
    }

    public static void main(String[] args) {
        SlidingWindowMax swm = new SlidingWindowMax();
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int[] result = swm.maxSlidingWindow(nums, k);
        for (int val : result) {
            System.out.print(val + " ");
        }
    }
}

Applications of Monotonic Stack

• Next Greater/Smaller Element: Finding the next larger/smaller element to the right (or left) of each element in an array. For example, given an array, a monotonic stack can help find the next greater element for each element.
• Sliding Window Maximum: Using a monotonic decreasing stack to maintain the maximum value within a sliding window.
• Trapping Rain Water: Using a monotonic decreasing stack to efficiently calculate how much water can be trapped between pillars.
• Largest Rectangle in Histogram: Using a monotonic increasing stack to find the maximum rectangle area that can be formed by each bar in a histogram.

Advantages and Disadvantages of Monotonic Stack

Advantages

• Efficiency: The monotonic stack reduces the time complexity to $O(n)$ in many problems, as each element is pushed and popped from the stack only once. This is a significant advantage for certain problems.
• Space Saving: Compared to brute-force methods that explore all possible combinations, the monotonic stack only requires linear space.

Disadvantages

• Limited Use Cases: Monotonic stacks are mainly suitable for problems that involve sequential data processing and require updating data states based on the current element.
• Additional Space Overhead: Although it reduces time complexity, the monotonic stack requires extra space for the stack itself, which may not be suitable for memory-constrained environments.